/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 21:49
 */
import java.util.*;


// 5. 最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        // 仅由数字和英文字符组成
        //要找到的是这个字符串中的最长回文子串 并返回这个字符串
        //想法：动态规划
        //新建一个dp数组，dp[i]的含义：以i下标的字符作为回文串的中心 然后向2边扩散所找到的最长的回文子串的长度
        int len=s.length();
        int[] dp=new int[len];
        //链表可以进行头插和尾插所以存放回文子串的数据结构，我们选择链表
        LinkedList<LinkedList<Character>> list=new LinkedList<>();
        LinkedList<Character> string=new LinkedList<>();
        //使用链表来存储 我们每次找到的回文串
        // 使用 addLast() 在尾部添加元素
        // 使用 addFirst() 在头部添加元素

        //中心扩散法
        //每次遍历到的下标值作为中心，来往2边扩散寻找，然后并且把找到的子字符串和这个子字符串的长度存起来

        //每次找到的子字符串的长度存在dp数组中，找到的子字符串存到 链表 string 中
        //最后把 string 都汇总到list中

        //初始化一下0下标位置的信息
        dp[0]=1;
        string.addFirst(s.charAt(0));
        list.add(new LinkedList<>(string));

        //开始状态的转移，填写dp表
        for(int i=1;i<len;i++){
            //strings用来记录中间状态（中间路径）
            LinkedList<Character> strings=new LinkedList<>();


            //第一种方式：从i下标开始往前和往后找，方便理解的例子： ab ba
            //i的值不能变，所以让ret=i，进行后续操作
            int ret=i;
            //以i下标值作为回文子串的中心，然后来找
            int j=i-1;

            LinkedList<Character> string1=new LinkedList<>();
            //string1来存放第一种方式找到的回文串
            int sum1=0; // 用来存放第一种方式找到的回文串的长度

            while(j>=0 && ret<len){
                if(s.charAt(j)==s.charAt(ret)){
                    sum1+=2;
                    string1.addFirst(s.charAt(j));
                    string1.addLast(s.charAt(ret));
                    //string[i]+=s.charAt(j);
                    //string[i]+=s.charAt(i);
                    j--;
                    ret++;
                }else{
                    break;
                }
            }

            //第二种寻找方式：以i下标作为中心开始往前和往后找，方便理解的例子： a  b  a
            j=i-1;
            ret=i+1;
            int sum2=1;//在第二种方式中，i下标的字符一定被包括了，所以初始化为1，用来存放第二种方式找到的回文串的长度
            LinkedList<Character> string2=new LinkedList<>();
            //string1来存放第二种方式找到的回文串
            string2.addFirst(s.charAt(i));
            //在第二种方式中，i下标的字符一定被包括了，所以初始化string2的时候，要记得先把i下标的字符放进去
            while(j>=0 && ret<len){
                if(s.charAt(j)==s.charAt(ret)){
                    sum2+=2;
                    string2.addFirst(s.charAt(j));
                    string2.addLast(s.charAt(ret));
                    //string[i]+=s.charAt(j);
                    //string[i]+=s.charAt(i);
                    j--;
                    ret++;
                }else{
                    break;
                }
            }

            //比较sum1和sum2的大小，较大值作为dp[i]的值填入，较大值对应的字符链表作为找到的中间路径放到list中
            if(sum1>sum2){
                strings=string1;
                dp[i]=sum1;
            }
            else{
                strings=string2;
                dp[i]=sum2;
            }

            //如果上面的2中寻找方式都没有找到包含i下标字符的回文串，此时它应该自成一派，
            //赋值它的 dp[i]=1 ,它的 中间字符路径为它自己本身
            if(dp[i]==0){
                dp[i]=1;
                strings.addFirst(s.charAt(i));
            }

            //到这里进行汇总，把这次找到的最好的，最合适的，长度最大的 回文字符路径 放到list中
            list.add(new LinkedList<>(strings));
        }

        //遍历dp[i]数组，找到长度最长回文子串对应的下标值
        int maxvalue=0;//用来寻找标注最长回文子串的长度
        int p=0;//用来记录长度最长回文子串对应的下标值
        for(int i=0;i<len;i++){
            if(dp[i]>maxvalue){
                maxvalue=dp[i];
                p=i;
            }
        }

        // System.out.println(maxvalue);

        //list中存的是字符类型，本题要返回的字符串类型，所以需要进行转换操作
        LinkedList<Character> num = list.get(p);
        String str="";
        for(Character ch : num){
            str+=ch;
        }


//返回我们所找到的最长回文子串（也可以说是返回最长回文子串中的一个，毕竟可能有多个回文子串的长度都满足条件嘛）
        return str;
    }
}
